1. Field of the Invention
The present invention relates to an image processing system and a method of providing the same, and more particularly, to an image processing system and method able to compress an original image, each pixel of which is expressed in RGB, RGBA or YUV, to an index image.
2. Description of Related Art
Recently, the amount of data for expressing a single image has significantly increased in response to gradual improvement in image quality. It is difficult to store a large number of images in a storage medium or it takes a long time to transfer image data through the network. Therefore, there is an increasing interest in a variety of methods for decreasing the amount of data related to images in order to decrease network traffics and reduce storage spaces.
A typical method for decreasing the size of an image, i.e. compressing the image, may be an image indexing method.
According to the image indexing method, an index and a pixel value of each pixel of a corresponding image (e.g. an RGB value, a YUV value, a differential value, or a quantized differential value) are stored in a table referred to as a palette or a reference table, and an actual image data is expressed as an index value of the palette. This image indexing method compresses the image by encoding (or storing) the index instead of the pixel value corresponding to the index while maintaining the index and the pixel value in the palette. The pixel value may be a color value of the pixel, or may be a data to be encoded (hereinafter referred to as an “encoding target data”), such as a differential value or a quantized differential value, with which a corresponding image is to be encoded (by, for example, Huffman coding). Although the pixel value stored in the palette may be a value expressing all of three colors, such as RGB values or YUV values, it may express each of R, G and B values.
FIG. 1A and FIG. 1B illustrate an example of an image indexing method using four colors. FIG. 1A illustrates a palette having pixel values consisting of four colors, and FIG. 1B illustrates an image having one index value of the index values of the palette shown in FIG. 1A as a pixel value. For example, referring to FIG. 1B, a pixel 1 shown in FIG. 1B has a pixel value 3. When the index is 3, the RGB values of the pixel 1 illustrated in FIG. 1B are R3, G3 and B3, as illustrated in FIG. 1A.
In the case illustrated in FIG. 1A and FIG. 1B, for the sake of convenience, the size of the palette is 4. In a typical image indexing method, the size of the palette may be 28(=256), and an image expressed by the image indexing method may have as many number of colors as the size of the palettes, i.e. 256 colors.
When the pixel value of each pixel of an image has RGB values or RGBA values, the size of one pixel ranges from 3 to 4 bytes. In contrast, when the same image is expressed by the image indexing method as above, the size of one pixel is 1 byte. When an image is expressed by the image indexing method, its size can be reduced to be smaller than the size of the image expressed by an RGB method. In addition, the compression efficiency of the image is improved when the image is compressed by the other methods.
However, the image indexing method has a problem in that the number of colors constituting an image is limited to be equal to or smaller than the size of the palette.
By the way, a pixel value corresponding to an index may be a data to be encoded (by, for example, Huffman coding). Therefore, the pixel value may be a differential value or a value obtained by quantizing the differential value. In this case, it is preferable that the pixel value corresponding to the index is expressed by a length (e.g. 1 byte) indicating the color value of the original pixel. Specifically, in the case in which the color value of the pixel is expressed by 1 byte, if the differential value indicating the difference between the color values of two pixels is negative, 9 bits are needed since 1 bit is used to indicate that the differential value is negative. In this case, the compression efficiency of an index image is significantly lowered, which is problematic.
In general, it is known that lossless compression does not require the sign bit of the differential value to be stored. However, lossy compression requires the sign bit of the differential value (i.e. the quantized differential value) to be stored. This will be described as follows with reference to FIG. 2.
FIG. 2 illustrates an example of an encoding method of the related art.
Referring to FIG. 2, the encoding method of the related art encodes target data, for example, p1 to pv from among a set of data (e.g. an image or a frame of video). The set of data may be an image, and the target data may be pixel values, i.e. data corresponding to pixels included in the image or the frame of the video.
In this case, an encoding system does not encode individual target data, for example, p1 to pv, but encodes a difference data, for example, pv-pred(pv), between a specific target data, for example, pv, and a predicted data, for example, pred(pv), of the specific target data pv in order to encode the specific target data pv. The difference data is also referred to as a differential value. It is well known that the predicted data pred(pv) may be a value corresponding to a pixel (e.g. a left pixel) close to the specific target data when the predicted data is an image, and that the predicted data may be implemented as a variety of forms.
As is well known, in the case of encoding difference data, for example, p1-pred(p1), p2-pred(p2), . . . , and pv-pred(pv), corresponding to the target data p1 to pv instead of directly encoding the target data p1 to pv, the compression ratio is high since there are more data having the same value. In addition, when a target data, for example, pv, is restored through decoding, an encoded difference data, for example, encoded(pv-pred(pv)), is decoded, and the target data pv is restored using the decoded data pv-pred(pv) and a predicted data, for example, pred(pv), for example, by adding the decoded data and the predicted data.
When the difference data p1-pred(p1), p2-pred(p2), . . . , and pv-pred(pv) are encoded, lossless compression is carried out unless the target data p1 to pv are compressed values (e.g. quantized values).
In this lossless compression, when encoded data is restored (like as pv), the value of the restored data is within a predetermined range since the restored data is an original target data. That is, when each of the target data p1 to pv is expressed by n bits (n is a natural number, for example, 8), the value of each target data is in a normal range of from 0 to 2n−1.
I.e. in lossless compression, even the difference data p1-pred(p1), p2-pred(p2), . . . , and pv-pred(pv) which to be encoded, are negative values, when the target data p1 to pv are restored (i.e. acquired) using the difference data p1-pred(p1), p2-pred(p2), . . . , and pv-pred(pv), the values of the data restored through decoding are within the normal range since the restoration data become the target data p1 to pv itself. Thus, even if at least one of the encoding target data, i.e. the difference data p1-pred(p1), p2-pred(p2), . . . , and pv-pred(pv), is a negative number, the values of the target data p1 to pv obtained from the difference data p1-pred(p1), p2-pred(p2), . . . , and pv-pred(pv) are always within the normal range.
It is also known, in this case, that the target data p1 to pv can be normally restored without the sign bits of the difference data p1-pred(p1), p2-pred(p2), . . . , and pv-pred(pv) being stored. Therefore, a lossless compression process in an encoding solution of the related art, such as joint photographic experts group-lossless (JPEG-LS) or portable network graphics (PNG), uses a variety of methods of selectively changing or neglecting some bits of pixel data without storing the sign bits.
However, in the case of lossy compression, the encoding target data should be data which is quantized value of the difference data p1-pred(p1), p2-pred(p2), . . . , and pv-pred(pv), i.e. quantization result data, for example, Q(p1-pred(p1)), Q(p2-pred(p2)), . . . , and Q(pv-pred(pv)). When restoration is performed using the quantization result data, the result of the restoration may differ from the target data p1 to pv itself with a certain error. Due to this error, the solution fails to ensure that the restoration data are within the normal range. Therefore, restoration is not normally performed unless the sign bits of the encoding target data Q(p1-pred(p1)), Q(p2-pred(p2)), . . . , and Q(pv-pred(pv)) are stored. In addition, the encoding solution of the related art also stores the sign bits of the encoding target data in the case of lossy compression.
In the case in which the sign bits are stored as above, at least one bit must be used for storing a sign bit, thereby lowering the compression ratio compared to the case in which no sign bits are stored. This problem still remains in the case in which the index image is used as described above and pixel values corresponding to the indexes are difference data, i.e. differential values (including quantized differential values).
The information disclosed in the Background of the Invention section is provided only for better understanding of the background of the invention and should not be taken as an acknowledgment or any form of suggestion that this information forms a prior art that would already be known to a person skilled in the art.